Multiprotocol Label Switching (MPLS) is a mechanism for packet routing that is widely used in high-performance computer networks. In an MPLS network, data packets are assigned labels, and packet-forwarding decisions are made solely on the contents of the labels, without the need to examine the network address of the packet itself. The MPLS architecture and label structure were originally defined by Rosen et al. in Requests for Comments (RFCs) 3031 and 3032 of the Internet Engineering Task Force (IETF) Network Working Group (2001), which are incorporated herein by reference.
MPLS is a network-layer protocol (Layer 3 in the Open Systems Interconnection [OSI] model), which is implemented by routers in place of or in addition to address-based routing. At the ingress to an MPLS network, a prefix is appended to the packet header, containing one or more MPLS labels. This prefix is called a label stack. According to RFC 3032, each label in the label stack contains four fields:                A 20-bit label value (commonly referred to as the label identifier or “label ID”).        A 3-bit traffic class field for QoS (quality of service) priority and ECN (explicit congestion notification) signaling (also referred to as the “EXP” or traffic class—“TC”—field).        A 1-bit bottom-of-stack flag, which is set to indicate that the current label is the last in the stack.        An 8-bit TTL (time to live) field.        
As explained in RFC 3031, any given router may use multiple different “label spaces,” with different label spaces being associated with different interfaces of the router, for example, so that label IDs are unique only within their given label space. Therefore, the term “label ID,” as used in the context of the present description and in the claims, should be understood to refer, where appropriate, to the couple (label space, label ID).
A router that routes packets based on these labels is called a label-switched router (LSR). According to RFC 3031, when an LSR receives a packet, it uses the label at the top of the stack in the packet header as an index to an Incoming Label Map (ILM). The ILM maps each incoming label to a set of one or more entries in a Next Hop Label Forwarding Entry (NHLFE) table. Alternatively, when packets arrive at the LSR unlabeled, a “FEC-to-NHLFE” function (FTN) maps each “Forwarding Equivalence Class” (FEC) to a set of one or more NHLFE table entries. In either case, each NHLFE indicates the next hop for the packet and an operation to be performed on the label stack. These operations may include replacing the label at the top of the stack with a new label, popping the label stack, and/or pushing one or more new labels onto the stack. After performing the required label stack operations, the LSR forwards the packet through the egress interface indicated by the NHLFE.
It is common practice to map a label in the ILM to a set of multiple NHLFEs for purposes of load balancing. In this context, equal-cost multi-path (ECMP) routing is commonly used as a routing strategy, in which next-hop packet forwarding to a single destination can occur over multiple “best paths,” which tie for top place in routing metric calculations. ECMP routing decisions are typically made per hop, by each router along the route of the packet through a network.
To improve load balancing in MPLS networks, Kompella et al. introduced the concept of “entropy labels,” in IETF RFC 6790, entitled “The Use of Entropy Labels in MPLS Forwarding” (2012), which is incorporated herein by reference. The authors point out that it is important when load balancing to ensure that packets belonging to a given “flow” are mapped to the same path, i.e., to the same sequence of links across the network. The entropy label, which is incorporated into the MPLS label stack that is pushed onto packets, serves as a key that can be used by transit LSRs in identifying flows for purposes of load balancing.